package DataStructure_ZL.排序;

import java.util.Arrays;
import java.util.Stack;

public class testSort {

    //直接插入排序
    public static void insertSort(int[] array) {
        if (array.length == 0) return;
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (temp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
    }

    //希尔排序
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            shell(array, gap);
        }
        shell(array, 1);
    }

    public static void shell(int[] array, int gap) {
        if (array.length == 0) return;
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (temp < array[j]) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = temp;
        }

    }

    //选择排序
    public static void selectSort(int[] array) {
        if (array.length == 0) return;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            int j = i + 1;
            for (; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }

    //冒泡排序
public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                }
            }
        }
    }


    //堆排序
    public void heapSort(int[] array) {
        //创建堆
        createHeap(array);
        //排序
        int end = array.length - 1;
        while (end >= 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }

    }

    private void createHeap(int[] array) {
        for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
            //向下调整
            shiftDown(array, i, array.length);
        }
    }

    private void shiftDown(int[] array, int p, int end) {
        int parent = p;
        int child = (2 * parent) + 1;
        while (child < end) {
            if (child + 1 < end && array[child] < array[child + 1]) child++;
            if (array[parent] < array[child]) {
                swap(array, parent, child);
                parent = child;
                child = child * 2 + 1;
            } else {
                break;
            }

        }
    }

    //快速排序
    public void quickSort(int[] array) {
        if (array.length == 0) return;
        quick(array, 0, array.length - 1);

    }

    private void quick(int[] array, int left, int right) {
        if (left >= right) return;
//        int i = partitionHoare(array, left, right);//Hoare法
//        int i = partitionHole(array, left, right);//挖坑法（推荐使用）
        int i = partition(array, left, right);//双指针法
        //优化 {
        //1、在某个区间的时候，使用直接插入排序【优化的区间内的比较】
        if (right - left + 1 <= 15) {
            //进行插入排序：
            insertSortRange(array, left, right);
            return;
        }
        //三数取中法【优化的是你本身的分割,减少递归的深度】
        int index = medianOfThreeIndex(array, left, right);
        swap(array, left, index);
        //  }
        quick(array, left, i - 1);
        quick(array, i + 1, right);
    }

    //快速排序  Hoare法
    private int partitionHoare(int[] array, int left, int right) {
        int i = left;
        int temp = array[left];
        while (left < right) {
            while (left < right && array[right] >= temp) right--;
            while (left < right && array[left] <= temp) left++;
            //到这里左边找到了比temp大的值右边找到了比temp小的，接下来互换
            swap(array, left, right);
        }
        swap(array, i, left);
        return left;
    }

    //快速排序  挖坑法
    private static int partitionHole(int[] array, int left, int right) {
        int temp = array[left];
        while (left < right) {
            //跳过比temp大的找到比temp小的索引
            while (left < right && array[right] >= temp) right--;
            array[left] = array[right];
            //跳过比temp小的找到比temp大的索引
            while (left < right && array[left] <= temp) left++;
            array[right] = array[left];
        }
        array[left] = temp;
        return left;
    }

    //快速排序  双指针法
    private int partition(int[] array, int left, int right) {
        int d = left + 1;
        int temp = array[left];
        //d会指向比temp大的值，i会指向比temp小的值（然后互换）
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < temp) {
                swap(array, d, i);
                d++;
            }
        }
        swap(array, left, d - 1);

        return d - 1;
    }

    //找到三个数中间大小的数字的下标 就是为了  较低高度
    private static int medianOfThreeIndex(int[] array, int left, int right) {
//        int mid = left + ((right - left) >>> 1);
        int mid = (left + right) / 2;
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    public static void insertSortRange(int[] array, int low, int end) {
        for (int i = low + 1; i <= end; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= low; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    //非递归实现快速排序
    public static void quickSortNor(int[] array) {
        if (array.length == 0) return;
        Stack<Integer> iu = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int i = partitionHole(array, left, right);

        //说明左边有两个以上的元素
        if (left + 1 < i) {
            iu.push(left);
            iu.push(i - 1);
        }
        //说明右边有两个以上的元素
        if (right - 1 > i) {
            iu.push(i + 1);
            iu.push(right);
        }

        while (!iu.isEmpty()) {
            right = iu.pop();
            left = iu.pop();

            i = partitionHole(array, left, right);

            //说明左边有两个以上的元素
            if (left + 1 < i) {
                iu.push(left);
                iu.push(i - 1);
            }
            //说明右边有两个以上的元素
            if (right - 1 > i) {
                iu.push(i + 1);
                iu.push(right);
            }
        }
    }

    //归并排序
    public static void mergeSort(int[] array) {
        mergeSortInternal(array, 0, array.length - 1);
    }

    private static void mergeSortInternal(int[] array, int low, int high) {
        if (low >= high) return;
        int i = (high - low) / 2 + low;
        mergeSortInternal(array, low, i);
        mergeSortInternal(array, i + 1, high);
        marge(array, low, i, high);
    }

    private static void marge(int[] array, int low, int i, int high) {
        //将两个数组有序合并
        int s1 = low;
        int e1 = i;
        int s2 = i + 1;
        int e2 = high;

        int[] iu = new int[high - low + 1];//存储合并的有序数组
        int k = 0;//新的流数组的下标
        //能进循环说明两个数组都有数值
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] > array[s2]) {
                iu[k++] = array[s2++];
            } else {
                iu[k++] = array[s1++];
            }

        }
        //将剩下的数据迁移
        while (s1 <= e1) iu[k++] = array[s1++];
        while (s2 <= e2) iu[k++] = array[s2++];

        //将排序好的部分数据添加到原数组
        for (int j = 0; j < iu.length; j++) array[j + low] = iu[j];
    }

    //计数排序
    public static void countSort(int[] array) {
        //先找到整个数组最大和最小的值，用来确定数组的大小
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) max = array[i];
            if (array[i] < min) min = array[i];
        }
        int[] count = new int[max - min + 1];

        for (int i = 0; i < array.length; i++) count[array[i] - min]++;

        //将排序好的数组迁移到原数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                array[index++] = i + min;
                count[i]--;
            }
        }

    }

    //数组互换指定索引数值
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {2, 52, 0, 59, 11, 88, 33, 100};
//        iu.insertSort(array);
//        testSort.shellSort(array);
//        testSort.selectSort(array);
//        testSort.bubbleSort(array);
//        iu.quickSort(array);
//        testSort.quickSortNor(array);
//        testSort.mergeSort(array);
        testSort.countSort(array);
        System.out.println(Arrays.toString(array));
    }
}
